<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
<script>
// 01背包问题

// 问题描述：给一个固定大小，能够携重W的背包，以及一组有价值重量的物品，
// 请找出一个最佳的方案，使得装入包中的物品重量不超过W且让背包总价值最大。
 
//    物品个数 n:5
//    物品重量 weights:[2，2，6，5，4]
//    物品价值 values:[6，3，5，4，6]
//    背包总容量 W:10
//    需求：怎么装使得总重量w<10，且value价值最大

// 思路：
// 假设一个函数为: f(i,j) :表示装入背包的最大价值
// 		其中的  i:表示装入的物品编号     
// 		其中的  j:表示背包目前的重量   (j<=w)

// 逻辑分析：

// 物品  物品  物品       背包重量从0~10变化    
// 重量  价值  编号       
//   w     v     i      0   1   2   3   4   5   6   7   8   9   10
//   2     6     0      0   0   6   6   6   6   6   6   6   6    6    对应
//   2     3     1      0   0   6   6   9   9   9   9   9   9    9    背包
//   6     5     2      0   0   6   6   9   9   9   9  11  11   14    价值
//   5     4     3      0   0   6   6   9   9   9  10  11  13   14    
//   4     6     4      0   0   6   6   9   9  12  12  15  15   15    


// 代码实现：

function knapsack(weights, values, w){
    var n = weights.length -1; // 获取盒子个数i  从盒子0开始
    var f=[[]]; //定义f的矩阵
    for(var j=0;j<=w;j++){
        // 盒子个数为1时
    	// 背包的重量j从0开始，一直到我们输入的w
        if(j<weights[0]){ // 背包的重量小于盒子0的重量，背包价值为0
        	f[0][j]=0;
        }else{
            f[0][j]=values[0]; // 否则背包价值为物品0的价值
            }
        }
    for(var j=0;j<=w;j++){
    	// 当盒子数不是1个时 
        for(var i=1;i<=n;i++){
            if(!f[i]){ // 创建新的一行
                f[i]=[];
            }
            if(j<weights[i]){ // 等于之前的最优值
                f[i][j]=f[i-1][j];
            }else{
                f[i][j]=Math.max(f[i-1][j],f[i-1][j-weights[i]]+values[i]);
                }
            }
        }
    return f[n][w];
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(a)


</script>


</body>
</html>